<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /**
         * 判断子序列
           输入：s = "abc", t = "ahbgdc"
           输出：true
           解释：判断s是否为t的子序列，是则返回true

           分析：动态规划
        */
        /* 
            时间：O(n)
            空间：O(n * m)
        */
        // 动态规划
        var maxSubArray = function(s, t) {
            if (s.length === t.length && s !== t) {
                return false
            }
            // 初始化
            let dp = new Array(s.length + 1).fill(0).map(() => new Array(t.length +  1).fill(0))
            for (let i = 1; i <= s.length; i++) {
                for (let j = 1; j <= t.length; j++) {
                    // 比较的是i-1和j-1的的字符是否相同
                    if (s[i - 1] === t[j - 1]) {
                        dp[i][j] = dp[i - 1][j - 1] + 1
                    } else {
                        // 和最长公共子序列的区别在这：最长公共子序列是Math.max(dp[i - 1][j], dp[i][j - 1])
                        dp[i][j] = dp[i][j - 1]
                    }
                }
            }
            return dp[s.length][t.length] === s.length
        };
        // console.log(maxSubArray('abc', 'ahbgdc'));
        // console.log(maxSubArray('b', 't'));
        console.log(maxSubArray('bb', 'ahbgdc'));
    </script>
</body>

</html>